package graphmanip.thinning;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

import commonfunctions.Matrix;

/**
 * Used to run the flow calculation for betweenness
 * 
 * @author Trevor Terris
 *
 */
public class FlowCalc 
{
	public static void calculate(Matrix flowGraph, Matrix weights, ArrayList<Point> problemEdges, ArrayList<Integer> nodesToCheck)
	{
		for (int i = 0; i < nodesToCheck.size(); i++)
		{
			HashMap<Integer, ArrayList<Integer>> path = shortestPath(nodesToCheck.get(i), weights);
			Iterator<Integer> pathIterator = path.keySet().iterator();
			while (pathIterator.hasNext())
			{
				int key = pathIterator.next();
				if (path.containsKey(key))
				{
					for (int k = 1; k < path.get(key).size(); k++)
					{
						Point edge = new Point(path.get(key).get(k - 1), path.get(key).get(k));
						if (problemEdges.contains(edge))
							flowGraph.set(flowGraph.get(edge.x, edge.y) + 1, edge.x, edge.y);
					}
				}
			}
		}
	}
	private static HashMap<Integer, ArrayList<Integer>> shortestPath (int start, Matrix weights)
	{
		HashMap<Integer, ArrayList<Integer>> outputPaths = new HashMap<Integer, ArrayList<Integer>>();
		ArrayList<Integer> nodesToExpand = new ArrayList<Integer>();
		nodesToExpand.add(start);
		ArrayList<Double> distanceToNodes = new ArrayList<Double>();
		distanceToNodes.add(0.0);
		ArrayList<ArrayList<Integer>> pathToNodes = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> initialPath = new ArrayList<Integer>();
		initialPath.add(start);
		pathToNodes.add(initialPath);
		while (nodesToExpand.size() > 0)
		{
			int currentNode = nodesToExpand.remove(0);
			double currentDistance = distanceToNodes.remove(0);
			ArrayList<Integer> currentPath = pathToNodes.remove(0);
			if (!outputPaths.containsKey(currentNode))
				outputPaths.put(currentNode, currentPath);
			if (currentPath.size() < 5)
			{
				double[] nodesForward = weights.singleRow(currentNode);
				double[] nodesBackward = weights.singleCol(currentNode);
				goThroughColOrRow(nodesToExpand, distanceToNodes, pathToNodes,
						currentDistance, currentPath, nodesForward, outputPaths);
				goThroughColOrRow(nodesToExpand, distanceToNodes, pathToNodes,
						currentDistance, currentPath, nodesBackward, outputPaths);
			}
		}
		return outputPaths;
	}
	private static void goThroughColOrRow(ArrayList<Integer> nodesToExpand,
			ArrayList<Double> distanceToNodes,
			ArrayList<ArrayList<Integer>> pathToNodes, double currentDistance,
			ArrayList<Integer> currentPath, double[] toExpand, 
			HashMap<Integer, ArrayList<Integer>> outputPaths) {
		for (int i = 0; i < toExpand.length; i++)
		{
			if (toExpand[i] > 0.0)
			{
				if (!currentPath.contains(i) && !outputPaths.containsKey(i))
				{
					int newNode = i;
					double newDistance = currentDistance + toExpand[i];
					ArrayList<Integer> newPath = new ArrayList<Integer>(currentPath);
					newPath.add(newNode);
					int start = 0;
					int end = distanceToNodes.size();
					while(end - start != 0)
					{
						if (distanceToNodes.get(start + (end - start)/2) < newDistance)
							start = start + (end - start)/2 + 1;
						else
							end = start + (end - start)/2;
					}
					nodesToExpand.add(start, newNode);
					distanceToNodes.add(start, newDistance);
					pathToNodes.add(start, newPath);
				}
			}
		}
	}
}
